Left Recursion

A left recursive grammar has a non-terminal \(S\) that there exists a production \(S \to^{+} S\, a\) for some \(a\). Such grammar won’t work for Recursive Descent Parsing.

However, we can rewrite left-recursive grammar with right-recursion. e.g., consider the following left recursive grammar

\[ S\to S\, a_{1} | S\, a_{2} | \dots | b_{1} | b_{2} | \dots, | b_{m} \]

The above is equivalent to the following right recursive grammar

\begin{split} S &\to m_{1} S' | \dots | b_{m} S' \\ S' &\to \epsilon | a_{1} S' | \dots | a_{n} S' \end{split}

More generally, left recursion has more general form, and can be eliminated automatically. See dragon book.